題目

https://leetcode.com/problems/median-of-two-sorted-arrays/

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

解答

C#

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int[] merged = mergeTwoSortedArrays(nums1, nums2);

        int length = merged.Length;
        if (length % 2 == 0)
        {
            int index = length / 2;
            return (merged[index - 1] + merged[index]) * 1.0 / 2;
        }
        else
        {
            int index = (length - 1) / 2;
            return merged[index];
        }
    }

    public int[] mergeTwoSortedArrays(int[] nums1, int[] nums2)
    {
        int[] merged = new int[nums1.Length + nums2.Length];

        int pointer1 = 0;
        int pointer2 = 0;
        for (int i = 0; i < merged.Length; i++)
        {
            if ((pointer1 < nums1.Length) && (pointer2 < nums2.Length))
            {
                if (nums1[pointer1] <= nums2[pointer2])
                {
                    merged[i] = nums1[pointer1];
                    pointer1++;
                }
                else if (nums1[pointer1] > nums2[pointer2])
                {
                    merged[i] = nums2[pointer2];
                    pointer2++;
                }
            }
            else if (pointer1 == nums1.Length)
            {
                for (int k = pointer2; k < nums2.Length; k++, i++)
                {
                    merged[i] = nums2[k];
                }
                break;
            }
            else if (pointer2 == nums2.Length)
            {
                for (int k = pointer1; k < nums1.Length; k++, i++)
                {
                    merged[i] = nums1[k];
                }
                break;
            }
        }
        return merged;
    }
}

結果

Runtime: 116 ms, faster than 99.11% of C# online submissions.

Memory Usage: 27.1 MB, less than 6.25% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

我有點訝異 LeetCode 竟然把這題放在 ！ 這一點都不 啊？！
我覺得 Climbing Stairs 還比較難一點...
而且不知道為什麼我看討論區的解答都寫得很複雜(真是黑人問號？)

這題主要是找出兩個已經排序號的 array 的 中位數 (Median)

什麼 中位數 (Median) 呢？我們來複習一下國中數學，根據 WiKi 的定義

對於有限的數集，可以通過把所有觀察值高低排序後找出正中間的一個作爲中位數。如果觀察值有偶數個，則中位數不唯一，通常取最中間的兩個數值的平均數作爲中位數。

舉例來說

{1, 2, 3, 4, 5} 

中位數 = 3

{1, 2, 3, 4, 5, 6}

中位數 = (3+4) / 2 = 3.5

所以這題只要

1. 把兩個 array merged
2. 排序
3. 判斷 array 長度是否可以整除2
   • 若可以整除 2 (%2 == 0)
     • index = array.Length / 2
     • array[index - 1] 及 array[index] 就會剛好在最中間的兩個數上
     • 相加除以 2 則為中位數
   • 若不能整除 2 (%2 != 0)
     • index = (length - 1) / 2
     • array[index] 則為中位數

效能調校

我本來一開始是直接 merged 再使用 Array.Sort 去做 1.與2.的步驟
後來我研究了一下 Array.Sort 的寫法

Microsoft Array.Sort Method

This method uses the introspective sort (introsort) algorithm as follows:

• If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.

• If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.

• Otherwise, it uses a Quicksort algorithm.

For arrays that are sorted by using the Heapsort and Quicksort algorithms, in the worst case, this method is an O(n log n) operation, where n is the Length of array.

Array.Sort 使用的是 Quicksort，效能不如預期（至於什麼是 Quicksort 有機會再講）
因為要 merge 的是兩個已經排序過的 arrays，所以這邊我是自己再另外寫一個排序方式 mergeTwoSortedArrays

1. Create a new int array merged, size = nums1.Length + nums2.Length
2. 宣告 pointer1 指向 nums1 的第一位
3. 宣告 pointer2 指向 nums2 的第一位
4. 比較 pointer1 是否超過 nums1.Length 及 pointer2 是否超過 nums2.Length
   • 若沒超過，就比較 nums1[pointer1] 及 nums2[pointer2] 的大小
     • 若 nums1[pointer1] 小餘 或 等餘 nums2[pointer2]
       • 將 nums1[pointer1] 放進 merged
       • pointer1++，指向 nums1 的下一個 int
     • 若 nums1[pointer1] 大餘 nums2[pointer2]
       • 將 nums2[pointer2] 放進 merged
       • pointer2++，指向 nums2 的下一個 int
   • 若 pointer1 等於 num1.Length
     • 代表 nums1 的 int 都已經放進 merged 裡，所以將 nums2 裡剩下的 int 都放到 merged 裡
   • 若 pointer2 等於 num2.Length
     • 代表 nums2 的 int 都已經放進 merged 裡，所以將 nums1 裡剩下的 int 都放到 merged 裡

這樣排序的方式，時間複雜度會從 Array.Sort 的 O(n log n) 變成 O(n)

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉